package com.ruoyi.system.exper;

import java.util.*;

public class Client0418 {

    // 选满
    public static int knapsack(int[] weight, int[] value, int maxweight) {

        // 动态规划  重量和 物品
        int n = value.length;
        int[][] dp = new int[n][maxweight + 1];
        try {
            for (int i = 0; i < n; i++) {
                for (int j = 1; j < maxweight + 1; j++) {
                    if (i == 0) { // 只选第一个的时候， 只有是整数倍才能有值，其他的都是最小值，，不能选的。
                        if (j >= weight[0] && j % weight[i] == 0) {
                            int k = j / weight[i];
                            // 第一个物品可以多次选择，只要满足条件
                            dp[i][j] = k * value[i];
                        } else {
                            dp[i][j] = Integer.MIN_VALUE;
                        }
                        continue;
                    }
                    if (j >= weight[i]) {
                        int k = j / weight[i];
                        for (int key = 0; key <= k; key++) {
                            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - key * weight[i]] + key * value[i]);
                        }
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }

                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        return dp[n - 1][maxweight];
    }

    // 买卖股票最大时机 动态规划解法
    public static int maxProfit(int[] prince) {
        // 定义二维数组表示最大利润，获取最大值 0代表持有 、1代表卖出
        int[][] dp = new int[prince.length][2];
        // 初始化值
        dp[0][0] = -prince[0];
        dp[0][1] = 0;
        int length = prince.length;
        for (int i = 1; i < length; i++) {
            // 第 i 天持有
            dp[i][0] = Math.max(dp[i - 1][0], -prince[i]);
            // 第i 天不持有
            dp[i][1] = Math.max(dp[i - 1][0] + prince[i], dp[i - 1][1]);
        }

        // 返回 i 天不持有
        return dp[prince.length - 1][1];
    }

    //  最大利润解法二
    public static int maxProfit1(int[] prince) {

        int length = prince.length;
        int small = prince[0];
        int maxprofit = 0;
        for (int i = 0; i < length; i++) {
            if (prince[i] > small) {
                maxprofit = Math.max(prince[i] - small, maxprofit);
            } else {
                small = prince[i];
            }
        }

        return maxprofit;
    }


    //  最近人的最大距离 相当于是求连续0最多的时候 可以用双指针
    public static int maxDistToClosest(int[] seats) {
        int left = -1;
        int right = 0;
        int max = 0;
        int length = seats.length;
        int begin = -1;
        for (int i = 0; i < length; i++) {
            if (seats[i] == 0) {
                right = i;
            } else {
                // 有人，移动左边指针 并计算当前最大值
                // 前面全是 0
                begin = begin == -1 ? i : begin;
                max = Math.max(max, right - left);
                left = i;
            }
        }
        int maxDist = (max + 1) / 2;
        // 左边有 0
        if (begin > 0) {
            maxDist = Math.max(maxDist, begin);
        }
        // 右边有 0
        if (right == length - 1) {
            maxDist = Math.max(maxDist, right - left);
        }
        return maxDist;
    }


    /**
     * 你有一个背包，最多能容纳的体积是V。
     * <p>
     * 现在有n种物品，每种物品有任意多个，第i种物品的体积为wi
     * <p>
     * （1）求这个背包至多能装多大价值的物品？
     * （2）若背包恰好装满，求至多能装多大价值的物品？
     *
     * @param v
     * @param n
     * @param nums
     * @return
     */

    public static ArrayList<Integer> knapsack(int v, int n, ArrayList<ArrayList<Integer>> nums) {

        // 这个最后的值是 随着体积和物品种类变化的。。这个可以用动态规划
        // 动规五部曲 找出下标变量
        int[][] dp = new int[v + 1][nums.size()]; // 在某个体积下，能够选择某些物品时，所能获取的最大值
        int size = nums.size();
        ArrayList<Integer> result = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < size; j++) {
                // 状态转移方程 当体积不变时，则可以选择物品种类
                // 只有体积大于时，才能
                Integer v1 = nums.get(j).get(0);
                Integer w1 = nums.get(j).get(1);
                if (j == 0) {
                    // 3.初始化
                    if (i >= v1) {
                        dp[i][j] = i / v1 * w1;
                    } else {
                        dp[i][j] = 0;
                    }
                    continue;
                }
                if (i >= v1) {
                    int key = i / v1;
                    for (int k = 0; k < key + 1; k++) {
                        dp[i][j] = Math.max(dp[i][j - 1], dp[i - k * v1][j - 1] + k * w1);
                    }

                } else {
                    dp[i][j] = dp[i][j - 1];
                }

            }
        }
        // 这是最大值
        result.add(dp[v][size - 1]);
        // 背包恰好装满的问题

        System.out.println("输出动态数组：");
        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < size; j++) {
                if (j == size - 1) {
                    System.out.println(dp[i][j]);
                    continue;
                }
                System.out.print(dp[i][j]);
            }
        }

        int[][] dp1 = new int[v + 1][nums.size()];
        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < size; j++) {
                // 状态转移方程 当体积不变时，则可以选择物品种类
                // 只有体积大于时，才能
                Integer v1 = nums.get(j).get(0);
                Integer w1 = nums.get(j).get(1);
                if (j == 0) {
                    // 3.初始化
                    if (i >= v1 && i % v1 == 0) {
                        dp1[i][j] = i / v1 * w1;
                    } else if (i != 0) {
                        dp1[i][j] = Integer.MIN_VALUE;
                    }
                    continue;
                }
                if (i >= v1) {
                    int key = i / v1;
                    dp1[i][j] = Integer.MIN_VALUE;
                    for (int k = 0; k < key + 1; k++) {
                        int max = Math.max(dp1[i][j - 1], dp1[i - k * v1][j - 1] + k * w1);
                        dp1[i][j] = Math.max(dp1[i][j], max);
                    }

                } else {
                    dp1[i][j] = dp1[i][j - 1];
                }

            }
        }

        System.out.println("输出动态数组1：");
        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < size; j++) {
                if (j == size - 1) {
                    System.out.println(dp1[i][j]);
                    continue;
                }
                System.out.print(dp1[i][j]);
            }
        }
        result.add(Math.max(dp1[v][size - 1], 0));
        return result;
    }

    //
//  6,2,[[5,10],[3,1]]

    public static void main(String[] args) {
        try {
            int[] price = {1, 2, 3, 4, 8};

            //  7,9,[[4,3],[2,1],[3,3],[2,5],[6,1],[7,4],[7,3],[3,2],[4,6]]
            ArrayList<Integer> integers = new ArrayList<>();
            integers.add(4);
            integers.add(3);
            ArrayList<Integer> integers1 = new ArrayList<>();

            integers1.add(2);
            integers1.add(1);
            ArrayList<Integer> integers2 = new ArrayList<>();

            integers2.add(3);
            integers2.add(3);
            ArrayList<Integer> integers3 = new ArrayList<>();

            integers3.add(2);
            integers3.add(5);

            ArrayList<Integer> integers4 = new ArrayList<>();

            integers4.add(6);
            integers4.add(1);
            ArrayList<Integer> integers5 = new ArrayList<>();

            integers5.add(7);
            integers5.add(4);
//            ArrayList<Integer> integers6 = new ArrayList<>();
//
//            integers6.add(2);
//            integers6.add(1);
//            ArrayList<Integer> integers7 = new ArrayList<>();
//
//            integers7.add(2);
//            integers7.add(1);
            ArrayList<Integer> integers8 = new ArrayList<>();
//
//            integers8.add(2);
//            integers8.add(1);
//            ArrayList<Integer> integers4 = new ArrayList<>();
//
//            integers3.add(2);
//            integers3.add(1);

            ArrayList<ArrayList<Integer>> integers10 = new ArrayList<>();
            integers10.add(integers);
            integers10.add(integers1);
            integers10.add(integers2);
            integers10.add(integers3);
            integers10.add(integers4);
            integers10.add(integers5);
            //    integers10.add(integers6);
            knapsack(7, 6, integers10);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    public static int knapsack(int n, String[] arr) {

        int length = arr.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        // 最少用的一个 和n 没关系
        int begin = 0;
        int max = 0;
        //  根据排名找key
        HashMap<Integer, Integer> rank = new HashMap<>();
        // 根据key 找排名
        HashMap<Integer, Integer> indexValuerank = new HashMap<>();
        for (int i = 0; i < length; i++) {
            if (arr[i].contains("p")) {
                Integer key = (int) arr[i].charAt(1);
                Integer value = hashMap.get(key);
                if (value == null) {
                    // 不存在
                    // 需要判断是否装满
                    if (n == 0) {
                        // 已经装满就需要移除一个了
                        // 获取最小的，移除
                        Integer integer = rank.get(begin++);
                        while (integer == null) {
                            integer = rank.get(begin);
                            begin++;
                        }
                        // 移除最小的
                        hashMap.remove(integer);
                        // 需要把key 和排名的映射取消掉
                        rank.remove(begin - 1);
                        indexValuerank.remove(key);

                    } else {
                        // 装进去了
                        hashMap.put(key, value);
                        // 排序也装上
                        rank.put(max++, key);
                        // 容量减1
                        n--;
                    }
                } else {
                    hashMap.put(key, value);
                }
                //  if (arr[i].charAt(1))
            }

            if (arr[i].contains("g")) {
                // 获取指令
                Integer key = (int) arr[i].charAt(1);
                Integer value = hashMap.get(key);
                if (value == null) {
                    return -1;
                } else {
                    // 存在
                    // 排名
                    Integer integer = indexValuerank.get(key);
                    // 移除以前的排名
                    rank.remove(integer);
                    rank.put(begin++, key);
                    // 添加新的排名
                    return value;
                }

            }

        }


        return 0;
    }

    public static int knapsack1(int[] forbidden, int a, int b, int target) {

        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int count = 0;
        return recyc(forbidden, a, b, target, 0, 0, hashMap, 0);

    }

    private static int recyc(int[] forbidden, int a, int b, int target, int x, int n, HashMap<Integer, Integer> hashMap, int count) {

        if (count > 1) {
            hashMap.put(x, Integer.MAX_VALUE);
            return 0;
        } else {
            // 退出条件1：达到目标值
            if (x == target) {
                if (hashMap.get(x) == null) {
                    hashMap.put(x, n);
                } else {
                    // 谁更小放谁
                    hashMap.put(x, Math.min(hashMap.get(x), n));
                }

                return 0;
            }
            // 退出条件2： 在禁止的范围内
            for (int i = 0; i < forbidden.length; i++) {
                if (forbidden[i] == x) {
                    hashMap.put(x, Integer.MAX_VALUE);
                    return 0;
                }
            }
            // 不能跳到负数位置
            if (x < 0) {
                return 0;
            }
            recyc(forbidden, a, b, target, x + a, n + 1, hashMap, count - 1);
            recyc(forbidden, a, b, target, x - b, n + 1, hashMap, count + 1);
        }

        // 递归
        return 0;

    }


    // 运用宽度优先算法，只是和这一行有关？   能用广度的是不是也基本能用深度算法？
    public int minimumJumps(int[] forbidden, int a, int b, int x) {

        // 记录已经跳过的位置 8001 :  x 最远距离，还没看懂，只想到了a >b,x+b 的场景。  2： 由于与该点的方向有关（向左，向右）
        int limit = 8000;
        boolean[][] visited = new boolean[8001][2];
        // 广度优先
        HashSet<Integer> forbiddenset = new HashSet<>();

        for (int i : forbidden) {
            forbiddenset.add(i);
        }

        // 家在禁止区域,不能到达
        if (forbiddenset.contains(x)) {

            return -1;
        }
        ArrayDeque<Integer[]> deque = new ArrayDeque<>();
        deque.offer(new Integer[]{0, 0});
        int layer = -1;
        while (!deque.isEmpty()) {
            // 得到这一层的宽度
            int size = deque.size();
            layer++;
            for (int i = 0; i < size; i++) {
                Integer[] poll = deque.poll();
                Integer location = poll[0];
                Integer backcount = poll[1];

                if (location == x) {
                    return layer;

                }
                //  禁止区域，不能跳
                // 如果访问过，跳过当前循环
                if (visited[location][backcount] || forbiddenset.contains(location)) {
                    continue;
                }
                // 标记访问
                visited[location][backcount] = true;

                // 开始装下一层的数据
                if (location + a < limit) {
                    // 向右走
                    deque.offer(new Integer[]{location + a, 0});
                }
                if (location - b < limit && location - b > 0 && backcount < 1) {
                    // 向走走
                    deque.offer(new Integer[]{location - b, 1});
                }

            }
        }
        return -1;
    }


}
